#include <stdio.h>

#define MAX_ROW 5
#define MAX_COL 5

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

struct point { int row, col; };
struct point path[512];
int path_len = 0;
int found = 0;

void print_maze(void) {
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++)
            printf("%d ", maze[i][j]);
        putchar('\n');
    }
    printf("*********\n");
}

void dfs(int row, int col) {
    if (found) return;
    
    if (row < 0 || row >= MAX_ROW || col < 0 || col >= MAX_COL)
        return;
    
    if (maze[row][col] != 0)
        return;
    
    maze[row][col] = 2;
    path[path_len].row = row;
    path[path_len].col = col;
    path_len++;
    
    if (row == MAX_ROW - 1 && col == MAX_COL - 1) {
        found = 1;
        print_maze();
        return;
    }
    
    print_maze();
    
    dfs(row, col + 1);
    if (found) return;
    
    dfs(row + 1, col);
    if (found) return;
    
    dfs(row, col - 1);
    if (found) return;
    
    dfs(row - 1, col);
    if (found) return;
    
    maze[row][col] = 0;
    path_len--;
}

int main(void) {
    if (maze[0][0] == 0) {
        dfs(0, 0);
    }
    
    if (found) {
        printf("正向路径:\n");
        for (int i = 0; i < path_len; i++) {
            printf("(%d, %d) ", path[i].row, path[i].col);
            if ((i + 1) % 5 == 0) putchar('\n');
        }
    } else {
        printf("No path!\n");
    }
    
    return 0;
}